package com.cwj.algorithm.heap;

import java.util.*;

/**
 * @author chenwujie
 * @date 2020/11/20 8:36
 */
public class Heap<E extends Comparable<? super E>> {
    private final transient Object[] elementData;
    private int n;
    private boolean isMin;

    public Heap(int capacity) {
        this.isMin = false;
        elementData = new Object[capacity + 1];
    }
    public Heap(int capacity, boolean isMin) {
        this.isMin = isMin;
        elementData = new Object[capacity + 1];
    }

    public void insert(E e) {
        elementData[++n] = e;
        swim(n);
    }

    public E removeFirst() {
        E head = elementData(1);
        exchange(1, this.n);
        elementData[n] = null;
        --n;
        sink(1);
        return head;
    }

    private void swim(int k) {
        if(isMin){
            while (k > 1) {
                if(greater(k / 2, k)){
                    exchange(k, k / 2);
                }
                k = k / 2;
            }
        }else{
            while (k > 1) {
                if(greater(k, k / 2)){
                    exchange(k, k / 2);
                }
                k = k / 2;
            }
        }
    }

    private void sink(int k) {
        sink(k, n);
    }
    private void sink(int k, int range) {
        if(isMin){
            while (k * 2  <= range) {
                int minIndex = k * 2;
                if (2 * k + 1 <= range && greater(2 * k, k * 2 + 1)) {
                    minIndex += 1;
                }
                if(minIndex <= range && greater(k, minIndex)){
                    exchange(minIndex, k);
                    k = minIndex;
                }else{
                    break;
                }
            }
        }else{
            while (k * 2  <= range) {
                int maxIndex = k * 2;
                if (2 * k + 1 <= range && greater(2 * k + 1, k * 2)) {
                    maxIndex += 1;
                }
                if(maxIndex <= range && greater(maxIndex, k)){
                    exchange(maxIndex, k);
                    k = maxIndex;
                }else{
                    break;
                }
            }
        }
    }

    private boolean greater(int i, int j) {
        return elementData(i).compareTo(elementData(j)) > 0;
    }

    private void exchange(int i, int j) {
        E temp = elementData(i);
        elementData[i] = elementData(j);
        elementData[j] = temp;
    }

    @SuppressWarnings("unchecked")
    private E elementData(int index) {
        return (E) elementData[index];
    }

    public static <E extends Comparable<? super E>> List<E> sort(List<E> src){
        return sort(src, false);
    }

    public static <E extends Comparable<? super E>> List<E> sort(List<E> src, boolean isMin){
        Heap<E> heap = new Heap<>(src.size(), isMin);
        // 初始化堆
        for (E e : src) {
            heap.insert(e);
        }
        // 循环遍历整个堆元素，下沉到末节点
        int len = src.size();
        while(len > 1){
            // 交换根节点与末节点元素
            heap.exchange(1, len);
            // 下沉根节点元素
            heap.sink(1, --len);
        }
        for (int i = 0; i < heap.n; i++) {
            src.set(i, heap.elementData(i + 1));
        }
        return src;
    }
}
